package leecode.array;

/**
 * @author humin
 * @title: FindOddEvenNum
 * @projectName java_demo
 * @description: 一个整数数组，
 * 1、一个数 出现奇数次  其他出现偶数次
 * 2、两个数  出现奇数次  其他出现偶数次
 * 时间复杂度O(n) 空间复杂度O(1)
 * 分别找出两种情况中出现奇数次的数
 * @date 2022/2/24 20:00
 */
public class FindOddEvenNum {
    public static void main(String[] args) {
        findOne();
        findTwo();
    }

    private static void findTwo() {
        int arr[] = {1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6};
        int eor = 0;
        for (int n : arr) {
            eor ^= n;
        }
        //  eor         0100 1011
        // ~eor         1011 0100
        // ~eor+1       1011 0101
        // eor&(~eor+1) 0000 0001
        int rightOne = eor & (~eor + 1);

        int onlyOne = 0;
        for (int a : arr) {
            if ((a & rightOne) != 0) {
                onlyOne ^= a;
            }
        }
        System.out.println(onlyOne);
        System.out.println(eor ^ onlyOne);
    }

    private static void findOne() {
        int arr[] = {1, 1, 2, 2, 2, 3, 3, 3, 3};
        int a = 0;
        for (int i = 0; i < arr.length; i++) {
            a = a ^ arr[i];
        }
        System.out.println(a);
    }


}
